package main

import (
	"math"
	"sort"
)

func isAlienSorted2(words []string, order string) bool {
	m := make(map[byte]byte)

	newWords := make([]string, len(words))
	copy(newWords, words)
	for i := 0; i < len(order); i++ {
		m[order[i]] = byte(i)
	}

	sort.Slice(newWords, func(i, j int) bool {
		isSmall := false
		min := int(math.Min(float64(len(newWords[i])), float64(len(newWords[j]))))

		k := 0
		for ; k < len(words[i]) && k < len(words[j]); k++ {
			if m[words[i][k]] < m[words[j][k]] {
				isSmall = true
				break
			} else if m[words[i][k]] > m[words[j][k]] {
				isSmall = false
				break
			}
		}
		if k == min {
			if len(newWords[i]) < len(newWords[j]) {
				isSmall = true
			}
		}
		return isSmall
	})

	//fmt.Println(newWords)
	for i := 0; i < len(newWords); i++ {
		if newWords[i] != words[i] {
			return false
		}
	}

	return true
}

func isAlienSorted(words []string, order string) bool {
	m := make(map[byte]byte)

	for i := 0; i < len(order); i++ {
		m[order[i]] = byte(i)
	}

	for i := 0; i < len(words)-1; i++ {
		w1, w2 := words[i], words[i+1]
		minL := min(len(w1), len(w2))
		j := 0
		for ; j < minL; j++ {
			if m[w1[j]] > m[w2[j]] {
				return false
			} else if m[w1[j]] < m[w2[j]] {
				break
			}
		}

		if j == minL && len(w1) > len(w2) {
			return false
		}
	}

	return true
}

func min(a, b int) int {
	if a > b {
		return b
	}
	return a
}
